package leetcode_121_140;

public class maxProfit_121 {
    /**
     * 选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票
     * 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     */
    public int maxProfit(int[] prices) {
        /**
         * 暴力解法显然很简单
         * 可以尝试问题简单化，求前一天卖出可以获得的最大利润
         * 逐次比较出最大值
         */
//        int res=0; //实时最大利润
//        int pre=0;//前一天卖出可以获得的最大利润
//        for(int i=1;i<prices.length;i++){
//            // 利润差
//            int diff = prices[i] - prices[i - 1];
//            pre=Math.max(0 , pre+diff);
//            //关键步骤，如果前面不管怎么卖，利润都是负数，不能影响后边的利润，直接赋值0
//            //否则就是  1 5 3    在 1 时入 3 时卖利润是  0 + 4 - 2  = 2
//            res = Math.max(res, pre);
//        }
//        return res;

        /**
         * 尝试动态规划
         */
        int n = prices.length;
        int[] dp = new int[2];
        dp[0] = -prices[0];  //初始化第0天持有的情况
        //dp[i][0] => dp[0]  代表第 i 天结束持有股票，手里的利润
        //dp[i][1] => dp[1] 代表第 i 天结束不持有股票，手里的利润
        for (int i = 1; i < n; i++) {
            //第 i 天结束，持有股票，该股票来自两种情况
            //1,昨天已经持有 dp[i-1][0] 简化为=> dp[0]
            //2,今天刚持有，即今天买入 -prices[i]
            dp[0] = Math.max(dp[0], -prices[i]);
            //第 i 天结束，不持有股票，两种情况
            //1,昨天已经不持有 dp[i-1][1] 简化为=> dp[1]
            //2,昨天还持有，今天刚卖
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
        }
        //不持有股票时，利润最大
        return dp[1];
    }


    /**
     * 与上一题的区别是这个可以购买多次
     * 任何时候 最多 只能持有 一股 股票。
     */
    public int maxProfit2(int[] prices) {
        /**
         * 发现规律，这段时间的利润最大和就是所有递增序列（股价连续的升高）的利润和
         * 易看出，这段升高的递增序列最大利润为连续的增大值之和
         * 我操了，泪目，自己一个人就想出来这种方法
         * 本来也想着是不是要用dp，后来突然脑子一抽就悟了
         * 1ms
         */
//        int res=0; //最大利润
//        int start=prices[0],end=prices[0];//一段递增序列的开头和结尾大小
//        for(int i=1;i<prices.length;i++){
//            // 利润差
//            int diff = prices[i] - prices[i - 1];
//            if(diff>0)
//                res+=diff;
//        }
//        return res;


        /**
         * 尝试动态规划
         * 可以购买多次
         * 但同时只能持有一个股票
         */
        int n = prices.length;
        int[] dp = new int[2];
        dp[0] = -prices[0];  //初始化第0天持有的情况
        // dp[0]  代表第 i 天结束持有股票，手里的利润
        // dp[1]  代表第 i 天结束不持有股票，手里的利润
        for (int i = 1; i < n; i++) {
            //第 i 天结束时，持有股票
            //1,昨天已经持有 ,今天没卖 dp[0]
            //2,今天刚持有，即今天买入 说明昨天没持有，dp[1]-prices[i]
            dp[0] = Math.max(dp[0], dp[1] - prices[i]);
            //第 i 天结束，不持有股票，两种情况
            //1,昨天结束时，不持有股票  dp[1]
            //2,昨天还持有，今天刚卖
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
        }
        //不持有股票时，利润最大
        return dp[1];
    }


    /**
     * 再次进阶，最多可以完成 两笔 交易。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     */
    public int maxProfit3(int[] prices) {
        /**
         * 初步思路是问题简化为找利润最大的交易分隔点
         * 使用数组动态规划从两个方向保存第一次交易和第二次交易在不同区间的最大利润
         * 设置分隔点
         * 独立解决，这个不算困难难度
         * 4ms
         */
//        if(prices.length<2)
//            return 0;
//        if(prices.length==2)
//            return Math.max(0,prices[1]-prices[0]);
//
//        int []first=new int[prices.length-1];        //first[i]        前 i 天的最大利润
//        int []second=new int[prices.length];      //second[i]   第 i 天到最后一天的最大利润
//        int pre=0;
//        for(int i=1;i<prices.length-1;i++){
//            pre=Math.max(0 , pre+prices[i] - prices[i - 1]);
//            first[i] = Math.max(first[i-1], pre);
//        }
//        pre=0;
//        for(int i=prices.length-2;i>=1;i--){
//            pre=Math.max(0 , pre+prices[ i+1] - prices[i]);
//            second[i] = Math.max(second[i+1], pre);
//        }
//
//        int res=0; //最大利润
//        for(int i=1;i<=prices.length-2;i++) {        //两次交易的分隔点
//            res=Math.max(res,first[i]+second[i]);
//        }
//        return res;
//    }


        /**
         * 正统动态规划
         * 设置5个状态
         * 0，之前没有操作
         * 1，已持有第一只股票
         * 2，已卖出第一只股票
         * 3，已持有第二只股票
         * 4，已卖出第二只股票
         */
        int n = prices.length;
        int[] dp = new int[4];
        dp[1] = -prices[0];
        dp[3] = -prices[0];
        for (int i = 1; i < n; i++) {
            //已持有第一只股票
            //该股票要么来自之前已经持有，要么是今天买入
            dp[1] = Math.max(dp[1], dp[0] - prices[i]);
            //已卖出第一只股票
            //之前卖了或今天卖了
            dp[2] = Math.max(dp[2], dp[1] + prices[i]);
            //已持有第二只股票
            //该股票要么来自之前已经持有，要么是今天买入
            dp[3] = Math.max(dp[3], dp[2] - prices[i]);
            //已卖出第二只股票
            //之前卖了或今天卖了
            dp[4] = Math.max(dp[4], dp[3] + prices[i]);
        }
        return dp[4];
    }
}
